package com.arron.algorithm.leetcodetop100.前缀和;

import com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组.最大子数组和_动态规划;
import com.arron.algorithm.leetcodetop100.滑动窗口.最大子数组和;

/**
 * 53. 最大子数组和 ,
 *   @see  最大子数组和
 *   @see 最大子数组和_动态规划
 */
public class 最大子数组和_前缀和 {



    public int maxSubArray(int[] nums) {
        if (nums.length<2){
            return nums[0];
        }
        int[] prefixSumArray = new int[nums.length+1];
        prefixSumArray[0] = 0;
        //初始化前缀和数组
        for (int i = 1; i < prefixSumArray.length; i++) {
            prefixSumArray[i] = prefixSumArray[i-1] + nums[i-1];

        }

        int minPreSum = Integer.MAX_VALUE;
        int maxSubSum = Integer.MIN_VALUE;
        for (int i = 1; i < prefixSumArray.length; i++) {

            minPreSum = Math.min(prefixSumArray[i-1],minPreSum);
            maxSubSum = Math.max(maxSubSum, prefixSumArray[i] - minPreSum);

        }
        return maxSubSum;


    }

    public static void main(String[] args) {
        最大子数组和_前缀和 maxArraySum = new 最大子数组和_前缀和();

        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxArraySum.maxSubArray(nums));

    }


}
